Turnbull China Bikeride/Turnbull China Bikeride - Disc 2.iso/BARNET/COMPILER/SATHER/!Sather/Library/Base/sa/int

Text File | 1996-08-03 | 28KB | 892 lines

---------------------------> Sather 1.1 source file <--------------------------
-- Copyright (C) International Computer Science Institute, 1994.  COPYRIGHT  --
-- NOTICE: This code is provided "AS IS" WITHOUT ANY WARRANTY and is subject --
-- to the terms of the SATHER LIBRARY GENERAL PUBLIC LICENSE contained in    --
-- the file "Doc/License" of the Sather distribution.  The license is also   --
-- available from ICSI, 1947 Center St., Suite 600, Berkeley CA 94704, USA.  --
--------> Please email comments to "[e-mail]". <----------

-- int.sa: Built-in integers.
-------------------------------------------------------------------
immutable class INT < $NUMBER{INT}, $HASH, $FMT is
   -- The most fundamental integer class. Signed, unsigned, and modular
   -- versions of arithmetic operations are provided. The names of
   -- unsigned operations begin with the letter "u". The names of
   -- modular operations begin with the letter "m". Negative numbers
   -- are represented using 2's complement. INT objects inherit from
   -- AVAL{BOOL}. The number of bits in the representation is `asize'
   -- and is implementation dependent. It must be at least 32, however
   -- (to ensure portability of INT literals up to this size). Many of
   -- the operations are specified to raise exceptions on overflow. They
   -- are guaranteed to do this if checking is enabled, but this may
   -- affect performance. Certain machines (with appropriate hardware)
   -- may perform these checks even when checking is not enabled. The
   -- modular operations are performed modulo 2^asize.
   --
   -- References:
   -- Keith O. Geddes, Stephen R. Czapor, and George Labahn, "Algorithms
   -- for Computer Algebra", Kluwer Academic Publishers, Boston, 1992.

   -- AVAL does not work yet.  For the moment leave out.
   -- include AVAL{BOOL} asize->;
   include COMPARABLE;

   const asize:INT:=32;
   -- Size in bits.

   -- Signed operations:

   plus(i:SAME):SAME is builtin INT_PLUS; end;
   -- The signed sum of self and `i'. Raises an exception on
   -- overflow, when enabled. Built-in.

   minus(i:SAME):SAME is builtin INT_MINUS; end;
   -- The signed difference between self and `i'. Raises an exception
   -- on overflow, when enabled. Built-in.

   negate:SAME is builtin INT_NEGATE; end;
   -- The signed negation of self. Same as zero minus self.
   -- Only raises an exception on the most negative value (which
   -- doesn't have a corresponding positive value in 2's complement.)
   -- Built-in.

   times(i:SAME):SAME is builtin INT_TIMES; end;
   -- The signed product of self and `i'. Raises an exception if the
   -- product can't be held in the result, when enabled. Built-in.

   div(i:SAME):SAME is builtin INT_DIV; end;
   -- The signed quotient of self and `i'. This and `mod' have the
   -- property that for non-zero `y', `x=x.div(y)*x + x.mod(y)'. Raises
   -- an exception when `i' is 0, when enabled. Built-in.

   mod(i:SAME):SAME is builtin INT_MOD; end;
   -- Signed remainder of self divided by `i'. This and `mod' have the
   -- property that for non-zero `y', `x=x.div(y)*x + x.mod(y)'. It's
   -- also true that `0 <= x.mod(y) < y.abs'. Raises an exception when
   -- `i' is 0, when enabled. Built-in.

   is_eq(i:SAME):BOOL is builtin INT_IS_EQ; end;
   -- True if self and `i' represent the same value.
   -- return self=i

   is_lt(i:SAME):BOOL is builtin INT_IS_LT; end;
   -- True if self is less than `i' as signed integers. Built-in.

   max(i:SAME):SAME is builtin INT_MAX; end;
   -- The larger of self and `i' as signed integers.  Built-in.

   min(i:SAME):SAME is builtin INT_MIN; end;
   -- The smaller of self and `i' as signed integers.  Built-in.

   at_least(x:SAME):SAME is
      -- Same as `max(x)'.
      return max(x)
   end;

   at_most(x:SAME):SAME is
      -- Same as `min(x)'.
      return min(x)
   end;

   within(x,y:SAME):SAME is
      -- Same as `max(x).min(y)'.
      return max(x).min(y)
   end;

   -- Conversion from other types:

   create(x:INT):SAME is return x end;
   create(x:INTI):SAME is return x.int end;
   create(f:FLT):SAME is return f.int end;
   create(f:FLTD):SAME is return f.int end;

   create(s:STR): SAME is builtin INT_CREATE_STR; end;

   int:INT is builtin INT_INT; end;
   -- An integer version of self.

   from_int(i:INT):SAME is
      -- Returns `i'.
      return i
   end;

   inti:INTI is
      -- An infinite precision version of self.
      return #INTI(self)
   end;

   flt:FLT is builtin INT_FLT; end;
   -- A floating point version of self. It is an error if the
   -- value cannot be held in a FLT.  Built-in.

   fltd:FLTD is builtin INT_FLTD; end;
   -- A double floating point version of self. It is an error
   -- if the value cannot be held in a FLTD.  Built-in.


   bool:BOOL is builtin INT_BOOL; end;
   -- A boolean from self.  Built-in.

   char:CHAR is builtin INT_CHAR; end;
   -- A character corresponding to the value of self. Built-in.

   c_unsigned_int:C_UNSIGNED_INT is builtin INT_C_UNSIGNED_INT; end;
   -- Convert to external C unsigned integer.  Built-in.

   -- Other computation:

   abs:SAME is builtin INT_ABS; end;
   -- The absolute value of self.  Built-in.

   square:SAME is builtin INT_SQUARE; end;
   -- The square of self.  Built-in.

   cube:SAME is
      -- The cube of self.
      return self*self*self
   end;

   pow(i:INT):SAME
   -- Self raised to the power `i'.
      pre i>=0 is
      r:SAME;
      case i
      when 0 then return 1
      when 1 then return self
      when 2 then return self*self
      when 3 then return self*self*self
      when 4 then r:=self*self; return r*r
      when 5 then r:=self*self; return self*r*r
      when 6 then r:=self*self; return r*r*r
      when 7 then r:=self*self; return self*r*r*r
      when 8 then r:=self*self; r:=r*r; return r*r
      when 9 then r:=self*self; r:=r*r; return self*r*r
      when 10 then r:=self*self; r:=self*r*r; return r*r
      else
     x ::= self; r := 1;
     loop
        -- r * x^i = self ^ i0
        if i.is_odd then r := r*x end;
        i := i.rshift(1);
        while!(i>0);
        x := x.square;
     end;
     return r;
      end;
   end;

   sqrt:SAME
   -- The largest integer whose square is smaller than self.
      pre self>=0
   is
      x::=fltd;
      r:SAME;
      if self=x.floor.int then return x.sqrt.floor.int
      else q::=1; r:=self;
     loop while!(q<=r); q:=4*q end;
     loop while!(q/=1); q:=q/4; h::=r+q; r:=r/2;
        if h<=r then r:=r-h; r:=r+q end end end;
      return r
   end;

   exp2:SAME pre self>=0 is return 0.set_bit(self) end;

   ten_pow:SAME pre self>=0 is return exp10 end;

   exp10:SAME
   -- Ten to the self power. Small values use lookup table for speed.
      pre self>=0
   is
      case self
      when 0 then return 1
      when 1 then return 10
      when 2 then return 100
      when 3 then return 1000
      when 4 then return 10000
      when 5 then return 100000
      when 6 then return 1000000
      when 7 then return 10000000
      when 8 then return 100000000
      when 9 then return 1000000000
      else return 10.pow(self) end
   end;

   num_digits:INT
   -- The number of decimal digits in non-negative self.
   -- Use binary search so that small values take only 3 compares.
      pre self>=0 is
      if self<10000 then
     if self<100 then
        if self<10 then return 1 else return 2 end
     else if self<1000 then return 3 else return 4 end end;
      else
     if self<1000000 then
        if self<100000 then return 5 else return 6 end
     else
        return (self/10000).num_digits+4;
        --r::=7; tst::=10000000;
        --loop
        --   if self<tst then return r end;
        --   r:=r+1; tst:=tst*10 end;
        --raise "INT::num_digits error."
     end
      end
   end;

   hash:INT is
      r::=self;

      -- We should try to get numbers away from each other, even if
      -- they don't collide.  For example, if SYS::id returns
      -- objects in consecutive aligned positions, we don't want to
      -- end up returning successive integers.  Unfortunately, it's
      -- not good enough to just multiply/add by some magic numbers,
      -- because that doesn't affect the randomness once passed
      -- through a mod function (for instance FSET etc. just use the
      -- rightmost bits, equivalent to mod by a power of two.)  Here
      -- a few steps of a shift generator are done.
      r:=r.bxor(r.lshift(17));
      r:=r.bxor(r.urshift(15));
      r:=r.bxor(r.lshift(17));
      r:=r.bxor(r.urshift(15));
      r:=r.bxor(r.lshift(17));
      r:=r.bxor(r.urshift(15));
      return r;
   end;

   -- Conversion into printable forms:

   str_in (s: FSTR, n, b: INT, f: CHAR): FSTR pre b.is_bet(2, 16) is
      -- Append a string representation of self to s using at least n digits
      -- to the base b and return s. If less then n digits are used for the
      -- representation of self (including its sign), the remaining left_most
      -- positions are filled with character f.
      --
      if is_nil then
     -- The nil value  (most negative number) cannot be negated -
     -- due to the inherent assymetry of the representation.
     -- There is no corresponding positive number
     x ::= self;
     divid: INT := x/b;
     rem1: INT := (x - divid*(b-1));
     rem: INT := rem1-divid;
     if rem > 0 then rem := rem-b;  divid := divid + 1; end;
     -- If divid was rounded up instead of down,manually divid to divid-1
     first_char: CHAR := rem.abs.digit_char;
     x := divid.abs;
     i ::= s.length;
     s := s+first_char;
     n := n - 1;
     loop s := s + (x%b).digit_char; x := x/b; n := n-1; until!(x = 0) end;
     s := s + '-'; n := n-1;
     loop while!(n > 0); s := s + f; n := n-1 end;
     j ::= s.length-1;
     loop while!(i < j);
        ch ::= s[i]; s[i] := s[j]; s[j] := ch; i := i+1; j := j-1
     end;
     return s;
     -- return #INTI(nil).str_in(s, n, b, f)
     --#FSTR("nil");
      else
     x ::= self.abs; i ::= s.length;
     loop s := s + (x%b).digit_char; x := x/b; n := n-1; until!(x = 0) end;
     if self < 0 then s := s + '-'; n := n-1 end;
     loop while!(n > 0); s := s + f; n := n-1 end;
     j ::= s.length-1;
     loop while!(i < j);
        ch ::= s[i]; s[i] := s[j]; s[j] := ch; i := i+1; j := j-1
     end;
     return s
      end
   end;


   str_in(s:FSTR):FSTR is
      -- Append a decimal string version of self to `s' and return it.
      return str_in(s, 0, 10, ' ')
   end;

   -- the shared buffer is actually faster, but not thread safe.
   -- private shared buf:FSTR;    -- Buffer for string output.

   str:STR is
      buf:FSTR;
      -- A decimal string version of self.
      buf.clear; buf:=str_in(buf); return buf.str
   end;

   fmt( f: STR ): STR
   is
      return BASE_FORMAT::fmt_int(self,f)
   end;

   digit_char:CHAR
   -- A character representing self. If self is between 0 and 9, it
   -- returns a digit. If between 10 and 15, returns 'A' thru 'F'.
      pre self.is_bet(0,15) is
      return "0123456789ABCDEF"[self]
   end;

   -- Integer properties:

   is_even:BOOL is builtin INT_IS_EVEN; end;

   is_odd:BOOL is builtin INT_IS_ODD; end;

   is_pos:BOOL is
      -- True if self is greater than zero.
      return self>0
   end;

   is_neg:BOOL is
      -- True if self is less than zero.
      return self<0
   end;

   is_zero:BOOL is
      -- True if self is zero.
      return self=0
   end;

   is_non_zero:BOOL is
      -- True if self is non-zero.
      return self/=0
   end;

   is_non_neg:BOOL is
      -- True if self is non-negative.
      return self>=0
   end;

   is_non_pos:BOOL is
      -- True if self is non-positive.
      return self<=0
   end;

   sign:SAME is
      -- -1,0,1 depending on the sign of self.
      -- Steele, 304
      if self<0 then return -1
      elsif self>0 then return 1
      else return 0 end
   end;

   is_bet(l,u:SAME):BOOL is builtin INT_IS_BETWEEN; end;
   -- True if self between l and u.  Built-in.

   is_between(l,u:SAME):BOOL is builtin INT_IS_BETWEEN; end;
   -- True if self between l and u.  Built-in.

   is_within(tolerance,val:SAME):BOOL is
      return (self-val).abs<=tolerance;
   end;

   is_eq(i1,i2:SAME):BOOL is
      -- True if self equals `i1' and `i2'.
      return self=i1 and self=i2 end;

   is_eq(i1,i2,i3:SAME):BOOL is
      -- True if self equals `i1', `i2', and `i3'.
      return self=i1 and self=i2 and self=i3 end;

   nil:SAME is
      -- The value to be used to represent no element in sets.
      -- The most negative value.
      return 1.lshift(asize-1)
   end;

   is_nil:BOOL is return self=1.lshift(asize-1); end;

   -- Unsigned operations:

   uplus(i:SAME):SAME is builtin INT_UPLUS; end;
   -- The unsigned sum of self and `i'. Raises an exception on
   -- overflow, when enabled. Built-in.

   uminus(i:SAME):SAME is builtin INT_UMINUS; end;
   -- The unsigned difference between self and `i'. Raises an
   -- exception on overflow or if the result would be negative,
   -- when enabled. Built-in.

   utimes(i:SAME):SAME is builtin INT_UTIMES; end;
   -- The unsigned product of self and `i'. Raises an exception if the
   -- product can't be held in the result, when enabled. Built-in.

   udiv(i:SAME):SAME is builtin INT_UDIV; end;
   -- The unsigned quotient of self and `i'. Raises an exception when
   -- `i' is 0, when enabled. Built-in.

   umod(i:SAME):SAME is builtin INT_UMOD; end;
   -- Unsigned remainder of self divided by `i'. Raises an exception
   -- when `i' is 0, when enabled. Built-in.

   is_ult(lhs:SAME):BOOL is
      if self>=0 and lhs<0 then return true end;
      if self<0 and lhs>=0 then return false end;
      -- both (self and lhs) have the same sign
      return self<lhs;
   end;

   is_uleq(i:SAME):BOOL is
      -- True if self is less than or equal to `i' as unsigned integers.
      return is_ult(i) or self=i
   end;

   is_ugt(i:SAME):BOOL is
      -- True if self is greater than `i' as unsigned integers.
      return i.is_ult(self)
   end;

   is_ugeq(i:SAME):BOOL is
      -- True if self is greater than or equal to `i' as unsigned
      -- integers.
      return i.is_ult(self) or self=i
   end;

   umax(i:SAME):SAME is
      -- The larger of self and `i' as unsigned integers.
      if self.is_ugt(i) then return self else return i end
   end;

   umin(i:SAME):SAME is
      -- The smaller of self and `i' as unsigned integers.
      if self.is_ult(i) then return self else return i end
   end;

   evenly_divides(i:SAME):BOOL is
      -- True if self evenly divides `i'.
      return i%self=0
   end;

   next_multiple_of(i:SAME):SAME
   -- The smallest value greater than or equal to self which is a
   -- multiple of `i'.
      pre i>0 is
      return ((self+i-1)/i)*i
   end;

   gcd(i:SAME):SAME is
      -- The greatest common divisor of self and `i'.
      -- The result is non-negative and `x.gcd(0)=x.abs'.
      -- Uses Euclidean algorithm. Geddes, et. al. p. 34.
      c::=abs; d::=i.abs;
      loop until!(d=0); r::=c.mod(d); c:=d; d:=r end;
      return c
   end;

   extended_gcd(i:SAME, out self_factor,out i_factor: SAME): SAME is
      -- The three parts of the return value `g', `g1', and `g2' are such
      -- that `g' is the greatest common divisor of self and `i' and
      -- `g1*self+g2*i=g'.
      -- Uses the extended Euclidean algorithm. Geddes, et. al. p. 36.
      c::=abs; d::=i.abs; c1::=1; d1::=0; c2::=0; d2::=1;
      loop until!(d=0);
     q::=c/d; r::=c-q*d; r1::=c1-q*d1; r2::=c2-q*d2;
     c:=d; c1:=d1; c2:=d2; d:=r; d1:=r1; d2:=r2
      end;
      self_factor :=  c1/(abs*c.abs);
      i_factor := c2/(abs*c.abs);
      return c.abs;
   end;

   lcm(i:SAME):SAME is
      -- The least common multiple of self and `i'.
      -- Geddes, et. al. p. 28.
      return (self*i).abs/gcd(i)
   end;

   is_prime:BOOL is
      -- True if self is a prime number.
      -- Replace by a faster algorithm.
      if 2.evenly_divides(self) then return false end;
      loop
     d::=3.step!((self.sqrt+2)/2, 2);
     if d.evenly_divides(self) then return false end
      end;
      return true
   end;

   is_relatively_prime_to(i:SAME):BOOL is
      -- True if self is relatively prime to `i'.
      return gcd(i)=1
   end;

   factorial:SAME is
      -- The factorial of self.
      -- Replace by faster algorithm.
      p::=1;
      loop p:=p*2.upto!(self) end;
      return p
   end;

   -- Operations modulo 2^asize:

   mplus(i:SAME):SAME is builtin INT_MPLUS; end;
   -- The sum of self and `i' modulo 2^asize. Never raises
   -- an exception. Built-in.

   mminus(i:SAME):SAME is builtin INT_MMINUS; end;
   -- The difference between self and `i' modulo 2^asize. Never
   -- raises an exception. Built-in.

   mnegate:SAME is builtin INT_MNEGATE; end;
   -- The additive inverse of self modulo 2^asize. Never raises an
   -- exception.

   mtimes(i:SAME):SAME is builtin INT_MTIMES; end;
   -- The product of self and `i' modulo 2^asize. Never raises
   -- an exception. Built-in.

   mdiv(i:SAME):SAME is builtin INT_MDIV; end;
   -- The unsigned quotient of self and `i'. Raises an exception when
   -- `i' is 0, when enabled. Built-in.

   mmod(i:SAME):SAME is builtin INT_MMOD; end;
   -- Unsigned remainder of self divided by `i'. Raises an exception
   -- when `i' is 0, when enabled.

   -- Bitwise operations:

   bnot:SAME is builtin INT_BNOT; end;
   -- The bitwise complement of self.

   band(i:SAME):SAME is builtin INT_BAND; end;
   -- The bitwise and of self and `i'.

   bor(i:SAME):SAME is builtin INT_BOR; end;
   -- The bitwise inclusive or of self and `i'.

   bxor(i:SAME):SAME is builtin INT_BXOR; end;
   -- The bitwise exclusive or of self and `i'.

   bnand(i:SAME):SAME is
      -- The bitwise nand of self and `i'.
      return band(i).bnot end;

   bnor(i:SAME):SAME is
      -- The bitwise nor of self and `i'.
      return bor(i).bnot end;

   beqv(i:SAME):SAME is
      -- The bits of res are 1 in positions where self and `i' have the
      -- same bit values.
      return bxor(i).bnot end;

   boole(i:SAME, rule:INT):SAME
   -- The bits of res are combinations of the corresponding bits of
   -- self and `i' combined according to a rule specified by `rule'.
   -- This must be a value between 0 and 15. The low order bit says
   -- what to map a 0 in self and a 0 in `i' to, the second bit of
   -- `rule' says what to map 0,1 to, the third bit defines 1,0 and
   -- the fourth 1,1.
      pre rule.is_bet(0,15) is
      case rule when 0 then return 0
      when 1 then return bor(i).bnot
      when 2 then return bnot.band(i)
      when 3 then return bnot
      when 4 then return band(i.bnot)
      when 5 then return i.bnot
      when 6 then return bxor(i)
      when 7 then return band(i).bnot
      when 8 then return band(i)
      when 9 then return bxor(i).bnot
      when 10 then return i
      when 11 then return bnot.bor(i)
      when 12 then return self
      when 13 then return bor(i.bnot)
      when 14 then return bor(i)
      when 15 then return -1
      else raise "INT::boole(SAME,INT):SAME err."
      end
   end;

   bcount:INT is
      -- The number of bits in self which are set to 1.
      r:SAME;
      if asize=32 then
     -- 32 bit version:
     r:=self.band(0b01010101010101010101010101010101)
           .uplus(self.urshift(1)
              .band(0b01010101010101010101010101010101));
     r:=r.band(0b00110011001100110011001100110011)
           .uplus(r.urshift(2).band(0b00110011001100110011001100110011));
     r:=r.band(0b00001111000011110000111100001111)
           .uplus(r.urshift(4).band(0b00001111000011110000111100001111));
     r:=r+r.rshift(8);
     r:=(r+r.rshift(16)).band(0b111111);
     -- No need to mask the last two steps since the bits can't
     -- interfere.
      else
     -- General size.
     -- Semi-clever version (fast when sparse but slow for dense):
     x::=self;
     loop until!(x=0); x:=x.band(x.uminus(1)); r:=r+1 end;
      end;
      return r
   end;

   lshift(i:INT):SAME is builtin INT_LSHIFT; end;
   -- The bits of self shifted left by `i' places with
   -- zeroes shifted in on the right.

   rshift(i:INT):SAME is builtin INT_RSHIFT; end;
   -- The bits of self shifted right by `i' places with
   -- bits equal to the first bit of self shifted in on the left.

   urshift(i:INT):SAME is builtin INT_URSHIFT; end;
   -- The bits of self shifted right by `i' places with
   -- zeroes shifted in on the left.

   lrotate(i:INT):SAME
   -- Left rotate the bits of self by `i' places.
      pre i.is_bet(0,asize)
   is
      return lshift(i).bor(urshift(asize-i))
   end;

   rrotate(i:INT):SAME
   -- Right rotate the bits of self by `i' places.
      pre i.is_bet(0,asize)
   is
      return urshift(i).bor(lshift(asize-i))
   end;

   bit(i:INT):BOOL is
      -- True if bit `i' of self is 1.
      return band(1.lshift(i))/=0
   end;

   set_bit(i:INT,b:BOOL):SAME is
      -- Self with bit `i' set to b.
      if b then return set_bit(i) else return unset_bit(i) end
   end;

   set_bit(i:INT):SAME is
      -- Self with bit `i' set to 1.
      return bor(1.lshift(i))
   end;

   unset_bit(i:INT):SAME is
      -- Self with bit `i' set to 0.
      return band((1.lshift(i)).bnot)
   end;

   octal_str:STR is
      -- The octal representation of self of the form "0o15".
      -- Self is interpreted as an unsigned integer.
      buf:FSTR;
      buf.clear; i::=self;
      loop
     buf:=buf + i.band(7).digit_char;
     i:=i.urshift(3);
     until!(i=0)
      end;
      buf:=buf + "o0";
      buf.to_reverse;
      return buf.str
   end;

   binary_str:STR is
      -- The binary representation of self of the form "0b100100".
      -- Self is interpreted as an unsigned integer.
      buf:FSTR;
      buf.clear; i::=self;
      loop
     buf := buf + i.band(1).digit_char;
     i:=i.urshift(1);
     until!(i=0)
      end;
      buf:=buf + "b0";
      buf.to_reverse;
      return buf.str
   end;

   hex_str:STR is
      -- The hexadecimal representation of self of the form "0x5A".
      -- Self is interpreted as an unsigned integer.
      buf:FSTR;
      buf.clear; i::=self;
      loop
     buf:=buf + i.band(15).digit_char;
     i:=i.urshift(4);
     until!(i=0)
      end;
      buf:=buf + "x0";
      buf.to_reverse;
      return buf.str
   end;

   lowest_bit:INT is
      -- The position of the lowest non-zero bit of self. -1 if none.
      if self=0 then return -1 end;
      if asize=32 then
     -- 32 bit version:
     x::=self; r::=31;
     z::=x.lshift(16); if z/=0 then x:=z; r:=r-16 end;
     z:=x.lshift(8); if z/=0 then x:=z; r:=r-8 end;
     z:=x.lshift(4); if z/=0 then x:=z; r:=r-4 end;
     z:=x.lshift(2); if z/=0 then x:=z; r:=r-2 end;
     z:=x.lshift(1); if z/=0 then x:=z; r:=r-1 end;
     return r
     --
     -- This implementation assumes that asize is a power of 2.
     -- if self=0 then return -1 end;
     -- x::=self; y::=asize/2; r:=asize-1;
     -- loop until(y=0); z::=x.lshift(y);
     -- if z/=0 then x:=z; r:=r-y end; y:=y.rshift(1) end; return r end;
     --
      else
     -- Straightforward way:
     loop i::=(asize-1).downto!(0);
        if lshift(i)/=0 then r::=asize-i-1; return r end
     end;
     return -1;
      end;
   end;

   highest_bit:INT is
      -- The position of the highest non-zero bit of self. -1 if none.
      if self=0 then return -1 end;
      if asize=32 then
     -- 32 bit version:
     x::=self; z::=x.urshift(16); r:INT;
     if z/=0 then x:=z; r:=r+16 end;
     z:=x.urshift(8); if z/=0 then x:=z; r:=r+8 end;
     z:=x.urshift(4); if z/=0 then x:=z; r:=r+4 end;
     z:=x.urshift(2); if z/=0 then x:=z; r:=r+2 end;
     z:=x.urshift(1); if z/=0 then x:=z; r:=r+1 end;
     return r;
      else
     --
     -- This implementation assumes that asize is a power of 2.
     -- if self=0 then return -1 end;
     -- x::=self; y::=asize/2;
     -- loop until(y=0); z::=x.urshift(y);
     --    if z/=0 then x:=z; r:=r+y end; y:=y.rshift(1) end;
     -- return r end;
     --
     -- Straightforward way:
     loop i::=1.upto!(asize-1);
        if rshift(i)=0 then return i-1 end
     end;
     return asize-1;
      end;
   end;

   log2:INT pre self>0 is return self.highest_bit end;

   is_pow_of_2:BOOL is return is_exp2 end;

   is_exp2:BOOL is
      -- returns true iff self is positive and a power of two

      res:BOOL:=false;
      if self > 0 then
     res := self.lowest_bit = self.highest_bit
      end;
      return res;
   end;

   next_pow_of_2:INT is return next_exp2 end;

   next_exp2:INT is
      -- for self positive it returns the p so that the following holds:
      -- p.is_pow_of_2 and p>=self>(p/2)

      res:INT:=0;
      bit:INT:=self.highest_bit;
      if ~self.is_pow_of_2 then
     bit := bit + 1;
      end;

      return res.set_bit(bit);
   end;

   low_bits(i:INT):INT
   -- The low `i' bits of self with 0 in the higher positions.
      pre i.is_bet(0,asize)
   is
      return band(1.lshift(i).uminus(1))
   end;

   high_bits(i:INT):INT is
      -- The high `i' bits of self with 0 in the lower positions.
      return band((1.lshift(asize-i).uminus(1)).bnot)
   end;

   aget(i:INT):BOOL is builtin INT_AGET; end;
   aset(i:INT,j:BOOL):INT is builtin INT_ASET; end;
   aelt!:BOOL is loop yield [asize.times!]; end; end;

   maxint:INT is builtin INT_MAXINT; end;
   minint:INT is builtin INT_MININT; end;

   const zero:SAME := 0;                -- See $NUMBER.
   const one: SAME := 1;
   maxval:SAME is return maxint; end;    -- See $NUMBER.
   minval:SAME is return minint; end;    -- See $NUMBER.

   -- Iters:

   times!  pre self>=0 is builtin INT_TIMESB; end;
   -- Yields self times without returning anything.

   times!:SAME pre self>=0 is builtin INT_TIMESB_INT; end;
   -- Yield successive integers from 0 up to self-1.

   for!(once i:SAME):SAME
   -- Yields `i' successive integers starting with self.
      pre i>=0 is builtin INT_FORB;
   end;

   up!:SAME is builtin INT_UPB; end;
   -- Yield successive integers from self up.

   upto!(once i:SAME):SAME is builtin INT_UPTOB; end;
   -- Yield successive integers from self to `i' inclusive.

   downto!(once i:SAME):SAME is builtin INT_DOWNTOB; end;
   -- Yield successive integers from self down to `i' inclusive.

   step!(once num,once step:SAME):SAME
   -- Yield `num' integers starting with self and stepping by `step'.
      pre num>=0
   is
      r::=self; last::=self+(num-1)*step;
      if step>0 then
     loop until!(r>last); yield r; r:=r+step end
      elsif step<0 then
     loop until!(r<last); yield r; r:=r+step end
      else
     loop num.times!; yield r end
      end
   end;

   stepto!(once to,once by:SAME): SAME
   -- Yield succeeding integers from self to `to' by step `by'.
   -- Might quit immediately if self is aleady `beyond'.
      pre by /= 0
   is
      r ::= self;
      if by>0 then
     loop until!(r>to); yield r; r := r + by end
      else
     loop until!(r<to); yield r; r := r + by end
      end
   end;

   sum!(i:SAME):SAME is
      -- Yields the sum of all previous values of `i'.
      r:SAME;
      loop r:=r+i; yield r end
   end;

   product!(i:SAME):SAME is
      -- Yields the product of all previous values of `i'.
      r::=1;
      loop r:=r*i; yield r end
   end;

end; -- class INT
-------------------------------------------------------------------